%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graph-theory-algorithms-book/
%%
%% Copyright (C) 2009--2011 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DontPrintSemicolon
\SetAlgoNoLine
%%
%% input
\KwIn{An alphabet $A$ of $n$ symbols. A weight list $W$ of size $n$
  such that $W[i]$ is the weight of $a_i \in A$.}
%%
%% output
\KwOut{A binary tree $T$ representing the Huffman code of $A$ and the
  root $r$ of $T$.}
\BlankLine
%%
%% algorithm body
$n \assign |A|$\;
$Q \assign A$\nllabel{alg:Huffman_tree:initialize_priority_queue}\tcc*[f]{minimum priority queue}\;
$T \assign$ empty tree\nllabel{alg:Huffman_tree:empty_binary_tree}\;
\For{$i \assign 1, 2, \dots, n-1$\nllabel{alg:Huffman_tree:for_loop:start}}{
  $a \assign \extractMin(Q)$\;
  $b \assign \extractMin(Q)$\;
  $z \assign$ node with left child $a$ and right child $b$\;
  add the edges $za$ and $zb$ to $T$\;
  $W[z] \assign W[a] + W[b]$\;
  insert $z$ into priority queue $Q$\nllabel{alg:Huffman_tree:insert_into_queue}\;
}
$r \assign \extractMin(Q)$\nllabel{alg:Huffman_tree:extract_tree_root}\;
\Return $(T, r)$\nllabel{alg:Huffman_tree:return_tree_and_root}\;
